# Definition for a Node.
class Node:
  def __init__(self, val, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right


class Solution:
  def treeToDoublyList(self, root: 'Node') -> 'Node':
    # 不要忘记判空
    if not root:
      return None
    # 中序遍历树，使用迭代法
    stack, res = [], list()
    while True:
      while root:
        stack.append(root)
        root = root.left
      if len(stack) > 0:
        node = stack.pop()
        res.append(node)
        root = node.right
      else:
        break
    head, tail = res[0], res[-1]
    if head == tail:
      head.left = head
      head.right = head
      return head
    for i in range(len(res)):
      if i == 0:
        res[i].left = tail
        res[i].right = res[i + 1]
      elif i == len(res) - 1:
        res[i].right = head
        res[i].left = res[i - 1]
      else:
        res[i].left = res[i - 1]
        res[i].right = res[i + 1]
    return head



def printList(root: 'Node'):
  while root:
    print('{}\t{}\t{}'.format(root.val, root.left.val, root.right.val))
    root = root.right


'''
STATUS: SOLVED
TRIES:  2
TIME:   48 MS
MEMORY: 14.1 MB
'''
if __name__ == "__main__":
  solution = Solution()
  # 创建测试二叉树
  root = Node(4)
  root.left = Node(2)
  root.right = Node(5)
  root.left.left = Node(1)
  root.left.right = Node(3)
  res = solution.treeToDoublyList(root)
  printList(res)
